package com.problem.sort;

import java.util.Random;

public class InsertSort {


    public static void main1(String[] args) {
        int[] a = new int[]{100,344,545,755,1241,1536,1537,1697,1855,2386,2466,2999,3009,2305,3418,3435,3767,3826,4080,4188,4317,4372,4706,4753,4845,4851,5189,5345,5594,5765,5768,6069,6127,6134,6495,6543,6656,7078,7086,7142,7167,7190,7609,7673,7692,8008,8352,8369,8917,9121,9863};
        print(sort(a,2350));
    }
    public static void main(String[] args) {
        long s1 = System.currentTimeMillis();
        System.out.println(s1);
        int len = 100;
        int max = 10000;
        int[]array1 = new int[len];
        Random r = new Random();
        for (int i = 0; i < len; i++) {
            array1[i] = r.nextInt(max);
        }
        long s2 = System.currentTimeMillis();
        int[]array2 = new int[len];
        System.arraycopy(array1,0,array2,0,len);
        System.out.println("生成数组：" + (s2-s1));
        System.out.println(array1.length);

        sort(array1);
        print(array1);
        System.out.println();
        long s3 = System.currentTimeMillis();
        System.out.println("array1:" + (s3-s2));

        int[] s = new int[]{array2[0]};
        for (int i = 1; i < len; i++) {
            System.out.println(array2[i]);
            print(s);
            s = sort(s,array2[i]);
        }
        print(s);
        System.out.println();
        long s4 = System.currentTimeMillis();
        System.out.println("array2:"+(s4-s3));
        boolean b = true;
        for (int i = 0; i < len; i++) {
            if (array1[i] - s[i] != 0) {
                b =false;
                System.out.println(i);
                System.out.println(array1[i] +" "+ s[i]);
                break;
            }
        }
        System.out.println(b);
    }

    private static void print(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }

    public static void sort(int arr[])
    {
        for(int i =1; i<arr.length;i++)
        {
            //插入的数
            int insertVal = arr[i];
            //被插入的位置(准备和前一个数比较)
            int index = i-1;
            //如果插入的数比被插入的数小
            while(index>=0&&insertVal<arr[index])
            {
                //将把 arr[index] 向后移动
                arr[index+1]=arr[index];
                //让 index 向前移动
                index--;
            }
            //把插入的数放入合适位置
            arr[index+1]=insertVal;
        }
    }



    //二分查找 插入排序---------------------------------------------------------------------------------
    public static int[] sort(int[] array, int a) {
        int length = array.length;
        int[] nArray = new int[length + 1];
        int idx = getIdx(array, a);
        //System.out.println("idx:" + idx);
        if (idx == 0) {
            System.arraycopy(array, 0, nArray, 1, length);
        } else if (idx == length) {
            System.arraycopy(array, 0, nArray, 0, length);
        } else {
            System.arraycopy(array, 0, nArray, 0, idx);
            System.arraycopy(array, idx, nArray, idx + 1, length - idx);
        }
        nArray[idx] = a;

        return nArray;

    }

    private static int getIdx(int[] array, int a) {
        int length = array.length;
        int l = 0, r = length - 1;
        int idx = (l + r) / 2;
        while (l < r) {
            if (array[idx] == a) {
                return idx + 1;
            } else if (array[idx] > a) {
                r = idx - 1;
                if (r < 0) {
                    return 0;
                }
                if (array[r] == a || array[r] < a) {
                    return r + 1;
                }
            } else {//array[idx]<a
                l = idx + 1;
                if (l > length) {
                    return length + 1;
                }
                if (array[l] == a || array[l] > a) {
                    return l;
                }
            }
            idx = (l + r) / 2;
        }
        return r==0?idx:idx+1;
    }
    //----------------------------------------------------------------------------
}
